//给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 
//
// 
//
// 进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？ 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,0]
//输出：3
// 
//
// 示例 2： 
//
// 
//输入：nums = [3,4,-1,1]
//输出：2
// 
//
// 示例 3： 
//
// 
//输入：nums = [7,8,9,11,12]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 300 
// -231 <= nums[i] <= 231 - 1 
// 
// Related Topics 数组 
// 👍 1025 👎 0


import java.security.PublicKey;
import java.util.HashSet;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
   public int firstMissingPositive(int[] nums) {
           int length = nums.length;
           for (int i = 0; i < length; i++) {
               while (nums[i] >= 1 && nums[i] <=length && nums[i] != i+1&& nums[i] != nums[nums[i] - 1])
                   swp(nums, i, nums[i] - 1);
           }

           for (int i = 0; i < length; i++) {
               if (nums[i]!=i+1){
                   return  i+1;
               }
           }
           return  length+1;
       }

       public void swp(int [] nums,int a,int b)
       {
           int temp=nums[a];
           nums[a]=nums[b];
           nums[b] = temp;
       }

}
//leetcode submit region end(Prohibit modification and deletion)
